The reliable transfer of data between devices within and across networks is a key requirement for today's technology. Examples of networks can range from end-user networks (e.g. home or company local area networks (LANs)) to higher-tier instances (e.g. core network). The communication between devices from different manufacturers is governed by standards and protocols. The Internet Protocol (IP), for instance, specifies the format of the addresses for devices to be enabled for communication over the Internet.
A network switch is a network node that connects devices together on a network, via individual ports, by using packet switching to receive, process and forward data to the destination port. Unlike less advanced network hubs, a network switch forwards data to one port (unicast) or to selected ones of the ports (multicast), rather than broadcasting the same data out of each of its ports.
The basic principle behind the switching function is to direct received data packets to the correct destinations, and more practically, to correct output ports. To do this, network nodes use a forwarding information bases (FIBs), tables which are used to associate destination addresses of data packets to be routed to corresponding output ports. The routing instance reads the destination address, which is included within the data packet under IP, looks up the FIB to find the corresponding routing data (e.g. output port), and then sends the data packet in the right direction or along the right link. A FIB is commonly used in network switching, and more sophisticated interfacing (e.g. bridging, routing, etc.).
The FIB can be in the form of a table which are looked up via key entries thereof. The key entries can be complete addresses, which are sometimes referred to as host routes. In the table, each key entry is associated to the routing information. The routing information for a given address is looked up via the associated key entry.
The transfer speed (bitrate) achievable by a given routing instance is strongly dependent upon the lookup speed, and many efforts have been made to improve lookup speed. For instance, it is common for a plurality of addresses having the same prefix to be associated to the same output port, in which case the FIB can include key entries in the form of one or more prefixes each leading to the routing data of multiple addresses, rather than listing the multiple addresses individually. This can shorten the FIB, and improve lookup time.
Some addresses share the same prefix as a given aggregate of other addresses, but cannot be grouped within the aggregate as they do not share the same output port. Such ‘exceptions’ are typically dealt with in FIBs by storing the exception addresses in the form of longer prefixes. Ultimately, a prefix can have the length of a complete address. A longest prefix match (LPM) algorithm can be used for the lookup. The LPM algorithm looks up the FIB for a match and, if more than one match is found (e.g. a shorter prefix and a longer prefix beginning with the same ‘root’ as the shorter prefix), selects the output port of the longest matching prefix.
In the past, various FIB schemes, and associated lookup algorithms have been developed in an effort to optimize transfer speed. For a given application, the solution ultimately retained by the designer, or later programmed in a given device, can depend on very practical factors. Indeed, such factors can include not only the intended function of the routing instance (type and quantity of data to be directed, number of output ports, etc.), but also factors such as the processor speed, the exact memory architecture (e.g. speed grade type(s) and corresponding quantity(ies) of memory cells). Indeed, there is often a motivation to downsize the FIB in order to allow storing it into higher-grade memory. Higher-grade memory is typically more expensive and more limited in quantity than lower-grade memory, but can be accessed in a faster manner by the processor.
Many LANs have only a single router provided in the form of a computer with a specialized design adapted to its specific purpose. It is quite typical for higher-tier networks or wide area networks (WANs) to have a plurality of physical routing devices (e.g. traditional routers, network switches) in a plurality of physical locations. Recent years have seen the development of network virtualization and key virtual network technologies such as virtual routers (VRs) and virtual private networks (VPNs) have emerged. Virtual networks often co-exist with and partially overlap one or more ‘physical’ network, and/or other virtual networks. Accordingly, more than one independent routing instance can coexist within a given routing device.
When more than one virtual router co-exist in a single physical routing device, they can compete for device resources, which can limit the transfer speed of each individual routing instance. For instance, each routing instance has a respective FIB stored in the device's memory.
When coexisting virtual routing functions are solicited for data packet routing simultaneously, one possibility would be to perform the virtual routing functions independently, in a sequential, alternating manner, with the processor accessing the corresponding FIB at each step of the sequence.
In at least some applications, a better overall transfer speed has been achieved by merging the FIBs of one or more coexisting routing instances into a single, merged FIB. Indeed, while the resulting merged FIB can represent more bits than a single one of the unmerged FIB's, an efficiency gain can nonetheless be achieved given the fact that only one (rather than more than one) FIB requires lookup.
Although various known schemes to deal with multiple routing instances on a single device have been satisfactory to a certain degree, there remains room for improvement.